# 四种领域搜索方法   两个关键路径改变方法
# 针对个体关键路径的操作

import numpy as np
import E_SetAdp
from D_Individual import *
from C_Load_Process_Map import *
import random

# 根据OS染色体某个基因位的下标获得该基因位工序号
# 注意：对应于加工图需要 -1
# 输入：OS染色体  基因位下标
# 输出：此基因位工序序号
def Get_Operation_Order(Job_Chromosome,index):
    print("模块：Critical\t方法：Get_Operation_Order(Job_Chromosome,index):")
    Num = 1                                                  # 初始化为1个
    for i in range(index):                                   # 遍历前工序 
            if Job_Chromosome[i] == Job_Chromosome[index]:   # 工件号相同
                    Num += 1                                   # 工序号加1
    return Num


# 根据工序编码下标获得机器编码的下标
# 输入：OS染色体 基因位下标
# 输出：基因位在MS染色体对应的下标
def Get_Machine_Index(Job_Chromosome,index):
    print("模块：Critical\t方法：Get_Machine_Index(Job_Chromosome,index):")
    Job_Order_Num = np.zeros(len(Job_Chromosome),dtype=int)   # 各工序工件的数量
    for i in range(len(Job_Chromosome)):
        Job_Order_Num[Job_Chromosome[i] - 1] += 1
    Temp = 0                                                  # 记录工序的第几工件数
    for j in range(index):
        if(Job_Chromosome[j] == Job_Chromosome[index]):
            Temp += 1   
    Pre_sum = 0                                               # 前工序的所有工序数量之和
    for m in range(Job_Chromosome[index] - 1):
        Pre_sum += Job_Order_Num[m]    
    return Pre_sum + Temp


# 计算工件前工序和后工序在OS染色体的下标
# 输入：OS染色体 工件序号 此工序序号
# 输出：前 当前 后工序 在OS染色体的下标
def Get_Pre_Operation_Post_Index(Job_Chromosome,Job_Index,Job_Operator_Num):
    print("模块：Critical\t方法：Get_Pre_Operation_Post_Index(Job_Chromosome,Job_Index,Job_Operator_Num):")
    Pre_Index = Index = Post_Index = -1                   # 初始化为-1 
    Num = 0
    for i in range(len(Job_Chromosome)):
            if Job_Chromosome[i] == Job_Index:            # 遍历工序集合
                    Num += 1
                    if Num == Job_Operator_Num - 1:       # 找到前序工序下标
                            Pre_Index = i
                            continue
                    if Num == Job_Operator_Num :          # 找到此工序下标
                            Index = i
                            continue
                    if Num == Job_Operator_Num + 1:       # 找到后续工序下标
                            Post_Index = i
                            continue        
    return  Pre_Index, Index,Post_Index                   # 如果是-1，则表示第一个工序或者最后一个工序


# 计算个体关键路径  
# 方法：工序的正反向调度位置不变  则为关键工序  关键路径可能不止一条
# 输入：个体 加工图
# 输出：个体关键路径决策变量 1 表示关键工序  工序信息     
def Get_Critiacl_Operation(Idv,Map):
    print("模块：Critical\t方法：Get_Critiacl_Operation(Idv,Map):")
    # 获得正向加工图
    Start_Time,End_Time,_,_ = E_SetAdp.Decoder(Idv,Map)
    # 将加工图反转
    Reverse_Map = []    # 反转加工图
    for i in range(Map.Job_Num):
        Temp = np.array(Map.Machine_Process_Map[i])
        Temp = Temp.tolist()
        Temp.reverse()
        Reverse_Map.append(Temp)

    # 将粒子的工序编码反转 ---注意python里面的地址机制
    Reverse_Job = np.array(Idv.Job_Chromosome)
    Reverse_Job = Reverse_Job.tolist()
    Reverse_Job.reverse()                             #反转工序编码

    # 将粒子的机器编码反转 ---按照每个工序进行反转
    Reverse_Machine = []                              # 反转机器编码
    Order_Num = np.zeros(Map.Job_Num,dtype=int)       # 每个工件的工序数量
    for i in Idv.Job_Chromosome:
        Order_Num[i - 1] += 1

    j = 0                                             # 临时变量
    for i in range(Map.Job_Num):
        Temp = []                                 # 对应每个工序
        Num = Order_Num[i]                        # 记录工件的数量
        while(Num != 0):
            Temp.append(Idv.Machine_Chromosome[j])
            j = j + 1
            Num -= 1 
        Temp.reverse()
        for m in Temp:
            Reverse_Machine.append(m)
    
    # 创建反转粒子 计算反转的所有工序的开始时间和结束时间
    Temp_idv = Individual()
    Temp_Reverse_Map = C_Load_Process_Map()       # 必须重新生成反转加工图
    Temp_Reverse_Map.Update_Map(Reverse_Map)
    Temp_idv.Update_Chromosome(Reverse_Job,Reverse_Machine,Temp_Reverse_Map)        
    # 反转的所有工序的开始时间和结束时间表
    Reverse_Start_Time,Reverse_End_Time,_,_ = E_SetAdp.Decoder(Temp_idv,Temp_Reverse_Map)
    # 将工序开始时间表和工序结束时间标反转过来
    for i in range(len(Start_Time)):
        Temp1 = Reverse_Start_Time[i]
        Temp2 = Reverse_End_Time[i]
        for j in range(len(Temp1)):                # 用最大值减去当前每一个点
            if Temp1[j] != 0:
                Temp1[j] = Idv.Adaptability[0] - Temp1[j]
        for m in range(len(Temp2)):
            if Temp2[m] != 0:
                Temp2[m] = Idv.Adaptability[0] - Temp2[m]
        Temp1 = Temp1.tolist()                     # 反转
        Temp1.reverse()
        Temp1 = np.array(Temp1)
        Temp2 = Temp2.tolist()
        Temp2.reverse()
        Temp2 = np.array(Temp2)
        Reverse_Start_Time[i] = Temp1              # 重新赋值
        Reverse_End_Time[i] = Temp2

    Temp = Reverse_Start_Time                          # 反转开始时间和结束时间
    Reverse_Start_Time = Reverse_End_Time
    Reverse_End_Time = Temp

    Critical_Flag = np.zeros(Map.Chromosome_Length,dtype = int)  # 关键工序标志
    for i in range(len(Start_Time)):        # 对比正反转加工图 两个上开始结束时间都一样就是关键工序
        Temp1 = Start_Time[i]
        Temp2 = End_Time[i]
        Temp3 = Reverse_Start_Time[i]
        Temp4 = Reverse_End_Time[i]
        for j in range(len(Temp1)):                          # 判断第j个工序是否为关键工序
            # 反转加工编码时候把最后完成时间可能会漏掉，但是不影响判断          
            if (Temp1[j]==Temp3[j] and Temp2[j]==Temp4[j] and Temp2[j]!=0) or (Temp1[j]==Temp3[j] and Temp2[j] == Idv.Adaptability[0]):
                Critical_Flag[j] = 1
    return Critical_Flag,Start_Time,End_Time,Reverse_Start_Time,Reverse_End_Time


# 关键路径变异 改变关键工序的顺序
# 方法：找到三个不同工件的关键工序 随机打乱他们顺序
# 输入：个体（带关键路径） 加工图
# 输出：更新后新个体
def Change_Critical_Order(Idv,Map):
    print("模块：Critical\t方法：Change_Critical_Order(Idv,Map):")
    Critical_Flag,_,_,_,_ = Get_Critiacl_Operation(Idv,Map)
    Temp = []                                               # 关键工序
    Temp_Index = []                                         # 关键工序在染色体下标
    for i in range(Map.Chromosome_Length):
        if Critical_Flag[i] != 0:
            Temp.append(Idv.Job_Chromosome[i])
            Temp_Index.append(i)
    
    Index1 = Index2 = Index3 = -1                           # 随机挑选三个不同工件的工序打乱随机顺序
    Index1 = random.choice(Temp_Index)
    Index2 = random.choice(Temp_Index)
    Index3 = random.choice(Temp_Index)
    # 保证工序来源于不同的工件
    while (Temp[Temp_Index.index(Index1)] == Temp[Temp_Index.index(Index2)] or
            Temp[Temp_Index.index(Index1)] == Temp[Temp_Index.index(Index3)] or
            Temp[Temp_Index.index(Index2)] == Temp[Temp_Index.index(Index3)]):
        Index1 = random.choice(Temp_Index)
        Index2 = random.choice(Temp_Index)
        Index3 = random.choice(Temp_Index)
    
    Sign = [Index1,Index2,Index3]                           # 挑选后 需要变异的基因位
    random.shuffle(Sign)                                    # 随机打乱
    while Sign == [Index1,Index2,Index3]:                   # 保证于原工序不同
        random.shuffle(Sign)
    Value1 = Temp[Temp_Index.index(Sign[0])]                # 通过下标索引到相应工序
    Value2 = Temp[Temp_Index.index(Sign[1])]
    Value3 = Temp[Temp_Index.index(Sign[2])]
    
    Temp[Temp_Index.index(Index1)] = Value1                 # 工序重新放回
    Temp[Temp_Index.index(Index2)] = Value2  
    Temp[Temp_Index.index(Index3)] = Value3           

    for i in range(len(Temp)):                              # 关键工序重新放回
        Idv.Job_Chromosome[Temp_Index[i]] = Temp[i] 
    New_Idv = Individual()                                  # 返回新个体
    New_Idv.Update_Chromosome(Idv.Job_Chromosome, Idv.Machine_Chromosome,Map)   # 将染色体更新
    return New_Idv


# 关键路径变异 改变关键工序的机器
# 方法：随机挑选n个工序随机换到其他机器上去
# 输入：个体（带关键路径） 加工图 需要转换关键工序数量
# 输出：更新后新个体
def Change_Critical_Machine(Idv,Map,Num):
    print("模块：Critical\t方法：Change_Critical_Machine(Idv,Map,Num):")
    Critical_Flag,_,_,_,_ = Get_Critiacl_Operation(Idv,Map)     
    Sign = [0] * Map.Chromosome_Length                        # 决策变量
    Sign_Num = 0
    while Sign_Num <= Num:                                    # 挑选n个关键工序
        for i in range(Map.Chromosome_Length):
            if Critical_Flag != 0:                
                R = random.uniform(0,1)                       # 随机数变量
                if Sign[i] == 0 and R < 0.2:
                    Sign[i] = 1
                    Sign_Num += 1

    for i in range(Map.Chromosome_Length):
        if Critical_Flag != 0 and Sign[i] == 1:             # 选中的关键工序
            Machine_Set = Map.Operation_Accessible_Machine_Index[Idv.Job_Chromosome[i] - 1][Get_Operation_Order(Idv.Job_Chromosome,i) - 1]
            Idv.Machine_Chromosome[Get_Machine_Index(Idv.Job_Chromosome,i)] = random.choice(Machine_Set)

    New_Idv = Individual()                                    # 返回新个体
    New_Idv.Update_Chromosome(Idv.Job_Chromosome, Idv.Machine_Chromosome,Map)   # 将染色体更新
    return New_Idv


############################################################################################################
# 策略：精准邻域搜索
# 原理：把关键路上上的关键算子移动到非关键路径上去,实现关键路径的缩短
# 操作：把关键块上的关键工序在不违背约束的情况下前移动后移
############################################################################################################


# 寻找关键块，根据关键路径，同一机器上连续加工的关键工序组成的块
# 方法：关键路径上 关键工序连着两个以上是关键块
# 输入：个体 加工图
# 输出：关键块信息 工序信息
def Get_Critical_Block(Idv,Map):
    print("模块：Critical\t方法：Get_Critical_Block(Idv,Map):")
    Critical_Flag,Start_Time,End_Time,Reverse_Start_Time,_ = Get_Critiacl_Operation(Idv,Map)
    Critical_Operation_Machine = [0] * Map.Chromosome_Length   # 关键工序所加工的机器
    for i in range(Map.Chromosome_Length):      
        if Critical_Flag[i] != 0:                              # 关键工序  机器号 没有-1
            Critical_Operation_Machine[i] = Idv.Machine_Chromosome[Get_Machine_Index(Idv.Job_Chromosome,i)]

    Critical_Block = []                                        #  工序块集合 两个两个连着的关键块
    for i in range(Map.Chromosome_Length):
        if Critical_Flag[i] != 0:                              # 关键工序
            for j in range(i+1,Map.Chromosome_Length):
                if Critical_Flag[j] != 0:
                    # 如果与当前工序在同一台机器上加工  
                    if Critical_Operation_Machine[i] == Critical_Operation_Machine[j]:
                        Time1 = End_Time[Critical_Operation_Machine[i]-1][i]    # 工序i的结束时间
                        Time2 = Start_Time[Critical_Operation_Machine[j]-1][j]  # 工序j的开始时间
                        if Time1 == Time2:                                      # 如果两个关键工序连着，说明是关键块                    
                            Temp = []                         # [开始加工时间，结束加工时间，工件号，工序号，当前加工机器号]
                            Temp1 = []                        # 工序i
                            Temp1.append(Start_Time[Critical_Operation_Machine[i]-1][i])
                            Temp1.append(End_Time[Critical_Operation_Machine[i]-1][i])
                            Temp1.append(Idv.Job_Chromosome[i])
                            Temp1.append(Get_Operation_Order(Idv.Job_Chromosome,i))
                            Temp1.append(Critical_Operation_Machine[i])

                            Temp2 = []      # 工序j
                            Temp2.append(Start_Time[Critical_Operation_Machine[j]-1][j])
                            Temp2.append(End_Time[Critical_Operation_Machine[j]-1][j])
                            Temp2.append(Idv.Job_Chromosome[j])
                            Temp2.append(Get_Operation_Order(Idv.Job_Chromosome,j))
                            Temp2.append(Critical_Operation_Machine[j])      

                            Temp.append(Temp1)    
                            Temp.append(Temp2)     
                            Critical_Block.append(Temp)                           
    Critical_Block_Copy = []                # 关键块合并 从两两的关键块 找到合并    
    Sign = [0] * len(Critical_Block)        # 标记所有元素是否访问
    while 0 in Sign:
        Index = 0
        Temp = []
        while Index <= (len(Critical_Block)-1):
            if Sign[Index] != 0:    # 此元素已经删除
                Index += 1
                continue
            if len(Temp) == 0:
                Temp.append(Critical_Block[Index][0])
                Temp.append(Critical_Block[Index][1])
                Sign[Index] = 1
            else:
                if Temp[len(Temp)-1] == Critical_Block[Index][0]:
                    Temp.append(Critical_Block[Index][1])
                    Sign[Index] = 1   
            Index += 1
        Critical_Block_Copy.append(Temp)
    return  Critical_Block_Copy,Critical_Flag,Start_Time,End_Time,Reverse_Start_Time     

                 
# 计算甘特图反向生成工序排序
# Insert:[插入机器,插入位置] 0表示第一个位置
def GanTeGraph_To_Operation(Idv,Map,End_Time,Temp_Block_Operation,Index,Insert):
    print("模块：Critical\t方法：GanTeGraph_To_Operation(Idv,Map,End_Time,Temp_Block_Operation,Index,Insert):")
    # 生成加工机器序列,与工序排序顺序一致
    Machine_Use_List = [-1] * len(Idv.Job_Chromosome)
    for i in range(len(End_Time)):
        Temp_End = End_Time[i]
        for j in range(len(Temp_End)):
            if Temp_End[j] == 0:
                    continue
            Machine_Use_List[j] = i
    # 每个机器上的加工工序集合[工件号,工序号]
    Machine_Operation_List = [[] for _ in range(Map.Machine_Num)]
    # 标记每个工序在工件中的顺序
    Job_Operation_Num = [1] * Map.Job_Num
    for i in range(Map.Chromosome_Length):
        Temp = []
        Temp.append(Idv.Job_Chromosome[i])
        Temp.append(Job_Operation_Num[Idv.Job_Chromosome[i] - 1])
        Job_Operation_Num[Idv.Job_Chromosome[i] - 1] += 1
        Machine_Operation_List[Machine_Use_List[i]].append(Temp)
    # 加工工序调整
    Temp_Machine_Operation_List = []
    Temp_Machine_Operation_List.append(Temp_Block_Operation[2])
    Temp_Machine_Operation_List.append(Temp_Block_Operation[3])
    # 在原位置删除掉要移动的关键工序
    Machine_Operation_List[Temp_Block_Operation[4] - 1].remove(Temp_Machine_Operation_List)
    # 在插入位置插入要移动的关键工序
    Machine_Operation_List[Insert[0]-1].insert(Insert[1],Temp_Machine_Operation_List)
    # 如果要插入的位置,导致工件工序加工顺序颠倒,则直接返回-1
    List = []
    # 先让其插入如果是逆序则直接退出
    for i in range(len(Machine_Operation_List[Insert[0]-1])):
        Temp = Machine_Operation_List[Insert[0]-1][i]
        if Temp[0] == Temp_Block_Operation[2]:
            List.append(Temp[1])  
    List_Copy = np.array(List)
    List_Copy = List_Copy.tolist()
    List_Copy = np.sort(List_Copy)
    if List != List_Copy.tolist():
        return [],[]
    # 新的工序排序染色体 
    Change_Job_Chromosome = [0] * len(Idv.Job_Chromosome)
    Sign = 0        # 标记新的工序排序染色体的每个位置
    # 标记每个工序在工件中的顺序
    Job_Operation_Num = [1] * Map.Job_Num
    # 标记每个机器 供随机选择机器
    Sign_Array = [i for i in range(Map.Machine_Num)]

    Machine_Sign = []
    while Sign <= Map.Chromosome_Length-1:            
        Machine_Choose = random.choice(Sign_Array)
        # 剔除不可行位置
        Machine_Sign.append(Machine_Choose)

        if len(Machine_Operation_List[Machine_Choose]) != 0:
            # 保证选择的要加工工序的顺序 
            if Job_Operation_Num[Machine_Operation_List[Machine_Choose][0][0]-1] == Machine_Operation_List[Machine_Choose][0][1]:
                # 工序加入染色体
                Change_Job_Chromosome[Sign] = Machine_Operation_List[Machine_Choose][0][0]
                # 工序已经完成加工,指向后续工序
                Job_Operation_Num[Machine_Operation_List[Machine_Choose][0][0]-1] += 1  
                Machine_Operation_List[Machine_Choose].remove(Machine_Operation_List[Machine_Choose][0])                
                Sign += 1
                Machine_Sign = []

        # 无法加工后续工序 此解违背了约束 set自动去重
        New_Machine_Sign = list(set(Machine_Sign))
        if len(New_Machine_Sign) == len(Sign_Array):
            return [],[]
        # 机器如果没有工序
        if len(Machine_Operation_List[Machine_Choose]) == 0: 
            Sign_Array.remove(Machine_Choose)

    Temp_Machine_Chromosome = Idv.Machine_Chromosome.tolist()
    Temp_Machine_Chromosome[Get_Machine_Index(Idv.Job_Chromosome,Index)] = Insert[0]
    Temp_Machine_Chromosome = np.array(Temp_Machine_Chromosome)
    Change_Job_Chromosome = np.array(Change_Job_Chromosome)
    return Change_Job_Chromosome,Temp_Machine_Chromosome   


# 关键块的关键算子移动到其他机器去
# 满足约束：该工序的加工时间小于等于(同时满足) 
# 1.插入位置的机器的前后相邻工序之间的时间段，后工序最迟加工时间减去前工序结束时间
# 2.此工件的前后相邻工序之间时间段，后工序最迟加工时间减去前工序结束时间
#
# 输出：从此邻域里找到目标值最小的个体返回   (可以设计一个函数 返回所有)
def Move_Ciritical_To_OtherMachine(Idv,Map):
        print("模块：Critical\t方法：Move_Ciritical_To_OtherMachine(Idv,Map):")
        # 1.寻找关键块
        Critical_Block,_,_,End_Time,Reverse_Start_Time = Get_Critical_Block(Idv,Map)
        
        Neighbour_Member = []           # 将此个体加入 此邻域
        Neighbour_Member_Value = []
        Neighbour_Member.append(Idv)
        Neighbour_Member_Value.append(Idv.Adaptability[0])

        # 2.寻找两个约束的交集的空闲位置
        # 2.1 找到关键块移动工序的可加工机器
        for i in range(len(Critical_Block)):
            Temp_Block = Critical_Block[i]
            
            for j in range(len(Temp_Block)):
                # [开始加工时间,结束加工时间,工件号,工序号,当前加工机器号]
                Temp_Block_Operation = Temp_Block[j]
                Map_Machine = Map.Machine_Process_Map[Temp_Block_Operation[2]-1][Temp_Block_Operation[3]-1]

                # 2.2 找到关键块移动工序的工件前后工序的时间间隔
                # 计算该 工序的 [前工件工序的结束时间,后工件工序的最迟开始时间]
                Block_Operation_Pre_Post_Time = [-1] * 2
                # 前工件工序,当前工序,的下标后工件工序在染色体上的下标
                Pre_Index,Index,Post_Index = Get_Pre_Operation_Post_Index(Idv.Job_Chromosome,
                                Temp_Block_Operation[2],Temp_Block_Operation[3])

                if Pre_Index == -1:     # 如果是此工件第一个工序
                    Block_Operation_Pre_Post_Time[0] = 0
                    Post_Operation_Machine = Idv.Machine_Chromosome[Get_Machine_Index(Idv.Job_Chromosome,Post_Index)] - 1
                    Block_Operation_Pre_Post_Time[1] = Reverse_Start_Time[Post_Operation_Machine][Post_Index]
                elif Post_Index == -1:    # 如果是此工件第最后一个工序
                    Block_Operation_Pre_Post_Time[1] = Idv.Adaptability[0]
                    Pre_Operation_Machine = Idv.Machine_Chromosome[Get_Machine_Index(Idv.Job_Chromosome,Pre_Index)] - 1
                    Block_Operation_Pre_Post_Time[0] = End_Time[Pre_Operation_Machine][Pre_Index]
                else:
                    # 前工件工序,后工件工序的加工机器
                    Pre_Operation_Machine = Idv.Machine_Chromosome[Get_Machine_Index(Idv.Job_Chromosome,Pre_Index)] - 1
                    Post_Operation_Machine = Idv.Machine_Chromosome[Get_Machine_Index(Idv.Job_Chromosome,Post_Index)] - 1
                    Block_Operation_Pre_Post_Time[0] = End_Time[Pre_Operation_Machine][Pre_Index]      
                    Block_Operation_Pre_Post_Time[1] = Reverse_Start_Time[Post_Operation_Machine][Post_Index]

                # 2.3 在时间间隔领域附近找可加工机器空闲位置
                # 计算 [机器前加工工序的结束时间,机器后加工工序的最迟开始时间] 
                # 如果与上面的时间间隔的交集小于 工序移动到这个机器上的加工时间 则插入
                # [机器前加工工序的结束时间,机器后加工工序的最迟开始时间,加工时间,加工机器,插入位置]
                Block_Machine_Pre_Post_Time = [] 
                for m in range(len(Map_Machine)):
                    if Map_Machine[m] == 9999:      # 不可加工机器
                        continue
                    if m == Temp_Block_Operation[4] - 1:    # 考虑其他机器 
                        continue
                    Insert_Index = []       # 记录插入的下标
                    for n in range(Map.Chromosome_Length):                        
                        if End_Time[m][n] == 0:             # 一个个找插入点
                            continue
                        Insert_Index.append(n)                    
                    Insertion_Location = 0                  # 标记插入位置
                    # 机器上第一个工序 先把第一个位置加上 0
                    Temp = [] 
                    Temp.append(0)
                    if len(Insert_Index) == 0:              # 如果该机器上没有加工工序
                        Temp.append(Idv.Adaptability[0])  
                    else:   
                        Temp.append(Reverse_Start_Time[m][Insert_Index[0]])  
                    Temp.append(Map_Machine[m])
                    Temp.append(m+1)
                    Temp.append(Insertion_Location)
                    Block_Machine_Pre_Post_Time.append(Temp) 
                    Insertion_Location += 1

                    for k in range(len(Insert_Index)):                                              
                        if k == len(Insert_Index) - 1:  # 机器上最后一个工序 
                            Temp = []
                            Temp.append(End_Time[m][Insert_Index[k]])
                            Temp.append(Idv.Adaptability[0])                                               
                        else:        
                            Temp = []
                            Temp.append(End_Time[m][Insert_Index[k]])
                            Temp.append(Reverse_Start_Time[m][Insert_Index[k+1]])
                        Temp.append(Map_Machine[m])
                        Temp.append(m+1)
                        Temp.append(Insertion_Location)
                        Insertion_Location += 1
                        Block_Machine_Pre_Post_Time.append(Temp)

                Insertion = []  # 最终可插入位置，可能不止一个
                for p in range(len(Block_Machine_Pre_Post_Time)):
                        Temp_Pre_Post_Time = Block_Machine_Pre_Post_Time[p]
                        Time_Interval = [-1] * 2        # 时间间隔
                        # 取交集
                        if Temp_Pre_Post_Time[0] <= Block_Operation_Pre_Post_Time[0]:
                            Time_Interval[0] = Block_Operation_Pre_Post_Time[0]
                        else:
                            Time_Interval[0] = Temp_Pre_Post_Time[0]

                        if Temp_Pre_Post_Time[1] <=  Block_Operation_Pre_Post_Time[1]:
                            Time_Interval[1] = Temp_Pre_Post_Time[1]
                        else:
                            Time_Interval[1] = Block_Operation_Pre_Post_Time[1]   

                        # 时间间隔大于加工时间，表示可以插入
                        if  (Time_Interval[1] - Time_Interval[0]) >= Temp_Pre_Post_Time[2]:
                            Temp = []
                            Temp.append(Temp_Pre_Post_Time[3])      # 插入机器
                            Temp.append(Temp_Pre_Post_Time[4])      # 插入位置
                            Insertion.append(Temp)

                # 3.将关键块中可移动的工序插入空闲位置---有效空闲,改变工序排序顺序
                # 插入工序
                for q in range(len(Insertion)):
                    Temp_Insert = Insertion[q]
                    Temp_Idv = Individual()
                    Temp_Job_Chromosome,Temp_Machine_Chromosome = GanTeGraph_To_Operation(Idv,
                            Map,End_Time,Temp_Block_Operation,Index,Temp_Insert)                        
                    if len(Temp_Job_Chromosome) == 0 and len(Temp_Machine_Chromosome) == 0:
                        continue
                    Temp_Idv.Update_Chromosome(Temp_Job_Chromosome, Temp_Machine_Chromosome, Map)                                    
                    Neighbour_Member.append(Temp_Idv)
                    Neighbour_Member_Value.append(Temp_Idv.Adaptability[0])
        # 从邻域所有个体中挑选makespan最小的                                    
        Choose_Index = Neighbour_Member_Value.index(min(Neighbour_Member_Value))
        if Choose_Index != 0:
            New_Idv = Individual()
            New_Idv.Update_Chromosome(Neighbour_Member[Choose_Index].Job_Chromosome,
                    Neighbour_Member[Choose_Index].Machine_Chromosome, Map)
            return New_Idv



# 关键块的关键算子移动到此机器上,因为是同机器上,加工时间都是一样的,调整加工顺序
# 满足约束：插入位置位于
# 该工序的前工序最早结束时间与关键块的最早加工时间之间存在时间片段
# 该工序的后工序的最迟加工时间与关键块的最早结束时间存在一个大于该工序加工时间的时间片段
# 输出：从此邻域里找到目标值最小的个体返回   (可以设计一个函数 返回所有)
def Move_Ciritical_To_SameMachine(Idv,Map):
    print("模块：Critical\t方法：Move_Ciritical_To_SameMachine(Idv,Map):")
    # 1.寻找关键块
    Critical_Block,_,Start_Time,End_Time,Reverse_Start_Time = Get_Critical_Block(Idv,Map)

    Neighbour_Member = []
    Neighbour_Member_Value = []
    Neighbour_Member.append(Idv)
    Neighbour_Member_Value.append(Idv.Adaptability[0])

    for i in range(len(Critical_Block)):
        Temp_Block = Critical_Block[i]
        # 关键块只有两个关键工序,直接交换他们位置
        if len(Temp_Block) == 2:                       
            # 找到第一个工序块在染色体上的位置
            _,Block_First_Index,_ = Get_Pre_Operation_Post_Index(Idv.Job_Chromosome,Temp_Block[0][2],Temp_Block[0][3])
            Block_Machine_Index = Temp_Block[0][4]-1
            Index = 0
            for j in range(Map.Chromosome_Length):
                if End_Time[Block_Machine_Index][j] == 0:
                    continue
                else:
                    Index += 1
                if j == Block_First_Index:
                    break       
            Insertion = []
            Insertion.append(Block_Machine_Index+1)   
            Insertion.append(Index)   
            Temp_Idv = Individual()                         # 生成新个体
            Temp_Job_Chromosome,Temp_Machine_Chromosome = GanTeGraph_To_Operation(Idv,
                    Map,End_Time,Temp_Block[0],Block_First_Index,Insertion)            
            if len(Temp_Job_Chromosome) == 0 and len(Temp_Machine_Chromosome) == 0:
                    continue
            Temp_Idv.Update_Chromosome(Temp_Job_Chromosome, Temp_Machine_Chromosome, Map)
            Neighbour_Member.append(Temp_Idv)               # 将新个体加入
            Neighbour_Member_Value.append(Temp_Idv.Adaptability[0])                          
        else:
            # 关键块首工序和尾工序的下标
            _,Block_First_Index,_ = Get_Pre_Operation_Post_Index(Idv.Job_Chromosome,Temp_Block[0][2],Temp_Block[0][3])
            _,Block_Last_Index,_ = Get_Pre_Operation_Post_Index(Idv.Job_Chromosome,
                                    Temp_Block[len(Temp_Block)-1][2],Temp_Block[len(Temp_Block)-1][3])
            # 遍历每个关键工序块
            for j in range(len(Temp_Block)):
                # 关键块中第一个工序和最后一个工序由于硬约束移动操作无效
                if j == 0 or j == len(Temp_Block) - 1:
                        continue                
                Temp_Block_Operation = Temp_Block[j]                # [开始加工时间,结束加工时间,工件号,工序号,当前加工机器号]                
                Block_Machine_Index = Temp_Block_Operation[4]-1     # 工件块所在机器
                Block_Operation_Pre_Time = [-1] * 2                 # 计算前工件工序结束加工时间与关键块首工序的最早加工时间                
                Block_Operation_Post_Time = [-1] * 2                # 计算后工件工序最迟加工时间与关键块尾工序的最早结束时间
                # 工件前后工序的下标
                Pre_Index,Index,Post_Index = Get_Pre_Operation_Post_Index(Idv.Job_Chromosome,
                                Temp_Block_Operation[2],Temp_Block_Operation[3])
                
                # 工件前后工序的加工机器
                Pre_Operation_Machine = Idv.Machine_Chromosome[Get_Machine_Index(Idv.Job_Chromosome,Pre_Index)] - 1
                Post_Operation_Machine = Idv.Machine_Chromosome[Get_Machine_Index(Idv.Job_Chromosome,Post_Index)] - 1                
                Block_Operation_Pre_Time[1] = Start_Time[Block_Machine_Index][Block_First_Index]    # 这两个时间是固定的
                Block_Operation_Post_Time[0] = End_Time[Block_Machine_Index][Block_Last_Index]

                if Pre_Index == -1:         # 如果是此工件第一个工序
                    Block_Operation_Pre_Time[0] = 0
                    Block_Operation_Post_Time[1] = Start_Time[Post_Operation_Machine][Post_Index]
                elif Post_Index == -1:      # 如果是此工件第最后一个工序
                    Block_Operation_Pre_Time[0] = End_Time[Pre_Operation_Machine][Pre_Index]
                    Block_Operation_Post_Time[1] = Idv.Adaptability[0]
                else:                       # 前工件工序,后工件工序的加工机器                    
                    Block_Operation_Pre_Time[0] = End_Time[Pre_Operation_Machine][Pre_Index]      
                    Block_Operation_Post_Time[1] = Start_Time[Post_Operation_Machine][Post_Index]
                Flag_Move_Forward = 1       # 标记是否可移动
                Flag_Move_Backward = 1                
                if Block_Operation_Pre_Time[0] >= Block_Operation_Pre_Time[1]:  # 确保有可插入位置
                    Flag_Move_Forward = -1
                if Block_Operation_Post_Time[0] >= Block_Operation_Post_Time[1]:
                    Flag_Move_Backward = -1

                # 确定插入位置
                Block_Machine_Pre_Post_Time = []            # [机器前加工工序的结束时间,机器后加工工序的最迟开始时间,插入位置]
                Insert_Index = []                           # 记录插入的下标
                for n in range(Map.Chromosome_Length):      # 一个个找插入点                        
                    if End_Time[Block_Machine_Index][n] == 0:
                        continue
                    Insert_Index.append(n)
                Insertion_Location = 0                      # 标记插入位置                
                Temp = []                                   # 机器上第一个工序 先把第一个位置加上 0
                Temp.append(0)
                Temp.append(Reverse_Start_Time[Block_Machine_Index][Insert_Index[0]])  
                Temp.append(Insertion_Location)
                Block_Machine_Pre_Post_Time.append(Temp) 
                Insertion_Location += 1

                for k in range(len(Insert_Index)):                                              
                    if k == len(Insert_Index) - 1:        # 机器上最后一个工序 
                        Temp = []
                        Temp.append(End_Time[Block_Machine_Index][Insert_Index[k]])
                        Temp.append(Idv.Adaptability[0])                                               
                    else:        
                        Temp = []
                        Temp.append(End_Time[Block_Machine_Index][Insert_Index[k]])
                        Temp.append(Reverse_Start_Time[Block_Machine_Index][Insert_Index[k+1]])
                    Temp.append(Insertion_Location)
                    Insertion_Location += 1
                    Block_Machine_Pre_Post_Time.append(Temp)    

                # 工件加工时间
                Block_Operation_Process_Time = Map.Machine_Process_Map[Temp_Block_Operation[2]-1][Temp_Block_Operation[3]-1][Block_Machine_Index]
                Insertion = []  # 最终可插入位置，可能不止一个
                for p in range(len(Block_Machine_Pre_Post_Time)):
                    # [机器前加工工序的结束时间,机器后加工工序的最迟开始时间,插入位置]
                    Temp_Pre_Post_Time = Block_Machine_Pre_Post_Time[p]
                    if (Temp_Pre_Post_Time[1] - Temp_Pre_Post_Time[0]) < Block_Operation_Process_Time:
                        continue
                    if Flag_Move_Forward != -1:         # 前移                        
                        if Temp_Pre_Post_Time[0] < Block_Operation_Pre_Time[1]:                            
                            if Temp_Pre_Post_Time[0] < Block_Operation_Pre_Time[0]:   # 太靠前的位置插入没有意义  
                                continue
                            else:
                                Temp = []
                                Temp.append(Block_Machine_Index+1)  
                                Temp.append(Temp_Pre_Post_Time[2])
                                Insertion.append(Temp)
                    if Flag_Move_Backward != -1:       # 后移                                       
                        if Temp_Pre_Post_Time[0] > Block_Operation_Post_Time[0]:
                            if (Temp_Pre_Post_Time[0] +  Block_Operation_Process_Time) > Block_Operation_Post_Time[1]:
                                continue
                            else:
                                Temp = []
                                Temp.append(Block_Machine_Index+1)  
                                Temp.append(Temp_Pre_Post_Time[2]-1)
                                Insertion.append(Temp)                                                                    
                    if Temp_Pre_Post_Time[0] == Block_Operation_Post_Time[0]:  # 后移特殊情况,直接放到关键块尾工序的后面
                        Temp = []
                        Temp.append(Block_Machine_Index+1)  
                        Temp.append(Temp_Pre_Post_Time[2]-1)
                        Insertion.append(Temp)    

                for q in range(len(Insertion)):         # 遍历所有可以插入位置
                    Temp_Insert = Insertion[q]
                    Temp_Idv = Individual()
                    Temp_Job_Chromosome,Temp_Machine_Chromosome = GanTeGraph_To_Operation(Idv,
                            Map,End_Time,Temp_Block_Operation,Index,Temp_Insert)                        
                    if len(Temp_Job_Chromosome) == 0 and len(Temp_Machine_Chromosome) == 0:
                            continue
                    Temp_Idv.Update_Chromosome(Temp_Job_Chromosome, Temp_Machine_Chromosome,Map)
                    Neighbour_Member.append(Temp_Idv)
                    Neighbour_Member_Value.append(Temp_Idv.Adaptability[0])
                                    
    Choose_Index = Neighbour_Member_Value.index(min(Neighbour_Member_Value))
    New_Idv = Individual()
    New_Idv.Update_Chromosome(Neighbour_Member[Choose_Index].Job_Chromosome,
                                Neighbour_Member[Choose_Index].Machine_Chromosome, Map)
    return New_Idv
        



